# 面试题 04.12. 求和路径
# 中等
# 相关标签
# 相关企业
# 提示
# 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
#
# 示例:
# 给定如下二叉树，以及目标和 sum = 22，
#
#               5
#              / \
#             4   8
#            /   / \
#           11  13  4
#          /  \    / \
#         7    2  5   1
# 返回:
#
# 3
# 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
# 提示：
#
# 节点总数 <= 10000
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def __init__(self):
        self.path_count = 0
        self.target_sum = 0

    def pathSum(self, root: TreeNode, target_sum: int) -> int:
        self.target_sum = target_sum
        self.iterate_path(root, [])
        return self.path_count
        pass

    def iterate_path(self, node: TreeNode, sum_list: List[int]):
        if node is None:
            return

        next_sum_list = [node.val]
        if node.val == self.target_sum:
            self.path_count = self.path_count + 1
        for sum_item in sum_list:
            next_sum = sum_item + node.val
            next_sum_list.append(next_sum)
            if next_sum == self.target_sum:
                self.path_count = self.path_count + 1

        self.iterate_path(node.left, next_sum_list)
        self.iterate_path(node.right, next_sum_list)
